package sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author RunningShrimp
 * @date 2021/6/16  13:37
 * @see <a href=""></a>
 */
public class ShellSort<E extends Comparable<E>> extends BaseSort<E> {
    @Override
    public void sort(E[] array) {
        int length = array.length;
        E temp;
        for (int step = length / 2; step >= 1; step /= 2) {
            for (int i = step; i < length; i++) {
                temp = array[i];
                int j = i - step;
                while (j >= 0 && less(array[j], temp)) {
                    array[j + step] = array[j];
                    j -= step;
                }
                array[j + step] = temp;
            }
        }
    }

    public static void main(String[] args) {
        Integer[] array = BaseSort.generateArray(5, 100);
        BaseSort<Integer> sort = new ShellSort<>();

        System.out.println("排序前：");
        sort.show(array);
        sort.sort(array);
        System.out.println("排序后");
        sort.show(array);
        System.out.println("是否有序：" + sort.isSorted(array));
    }
}
